package org.nkumar.stl;

import junit.framework.TestCase;

import java.util.List;
import java.util.Collections;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Random;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.RandomAccess;
import java.util.AbstractList;
import java.util.Comparator;

@SuppressWarnings({"JUnitTestMethodWithNoAssertions"})
public final class ListHelperTest extends TestCase
{
    public void testFind()
    {
        findTestEmpty();
        findTest(true);
        findTest(false);
    }

    private static void findTestEmpty()
    {
        assertEquals("find should return -1 if the list is empty",
                -1, ListHelper.find(Collections.EMPTY_LIST, ZERO));
        assertEquals("find should return -1 if the list is empty",
                -1, ListHelper.find(Collections.EMPTY_LIST, null));
        assertEquals("find should return -1 if the list is null",
                -1, ListHelper.find(null, ZERO));
        assertEquals("find should return -1 if the list is null",
                -1, ListHelper.find(null, null));
    }

    private static void findTest(final boolean raList)
    {
        assertEquals("find should locate object properly",
                0, ListHelper.find(getList("0,1,2", raList, false), ZERO));
        assertEquals("find should locate object properly",
                1, ListHelper.find(getList("0,1,2", raList, false), ONE));
        assertEquals("find should locate object properly",
                2, ListHelper.find(getList("0,1,2", raList, false), TWO));
        assertEquals("find should locate object properly",
                0, ListHelper.find(getList("2,1,2", raList, false), TWO));
        assertEquals("find should locate object properly",
                1, ListHelper.find(getList("1,2,2", raList, false), TWO));
        assertEquals("find should locate null properly",
                1, ListHelper.find(getList("0,N,2", raList, false), null));
        assertEquals("find should locate null properly",
                1, ListHelper.find(getList("0,N,N", raList, false), null));
        assertEquals("find should locate null properly",
                2, ListHelper.find(getList("0,1,N", raList, false), null));
        assertEquals("find should return -1 if the object is not found",
                -1, ListHelper.find(getList("0", raList, false), TWO));
        assertEquals("find should return -1 if the object is not found",
                -1, ListHelper.find(getList("0,N,1", raList, false), TWO));
        assertEquals("find should return -1 if the object is not found",
                -1, ListHelper.find(getList("0,1,2", raList, false), null));

        assertEquals("find should locate object properly",
                0, ListHelper.find(getList("1,2,2", raList, false).subList(2,3), TWO));
        assertEquals("find should locate object properly",
                -1, ListHelper.find(getList("1,2,2", raList, false).subList(2,2), TWO));
        assertEquals("find should locate object properly",
                1, ListHelper.find(getList("1,2,2,N", raList, false).subList(2,4), null));
    }

    public void testFindIf()
    {
        try
        {
            ListHelper.findIf(getList("1", true, false), null);
            fail("findIf should throw IllegalArgumentException if the passed predicate is null");
        }
        catch (IllegalArgumentException ignore)
        {
            //expected
        }
        //TODO add some more
    }

    public void testAdjacentFind()
    {
        adjacentFindTestEmpty();
        adjacentFindTest(true);
        adjacentFindTest(false);
    }

    private static void adjacentFindTestEmpty()
    {
        assertEquals("adjacentFind should return -1 if the list is empty",
                -1, ListHelper.adjacentFind(Collections.EMPTY_LIST));
        assertEquals("adjacentFind should return -1 if the list is null",
                -1, ListHelper.adjacentFind(null));
    }

    private static void adjacentFindTest(final boolean raList)
    {
        assertEquals("adjacentFind should return -1 if the size of the list is one",
                -1, ListHelper.adjacentFind(getList("0", raList, false)));
        assertEquals("adjacentFind should be able to locate the first adjacent equal objects",
                0, ListHelper.adjacentFind(getList("0,0,1,2", raList, false)));
        assertEquals("adjacentFind should be able to locate the first adjacent equal objects",
                2, ListHelper.adjacentFind(getList("0,1,2,2,3,4", raList, false)));
        assertEquals("adjacentFind should locate the first equal adjacent pair only",
                1, ListHelper.adjacentFind(getList("0,2,2,2,1,1", raList, false)));
        assertEquals("adjacentFind should locate the first equal adjacent pair only",
                0, ListHelper.adjacentFind(getList("1,1,1,1,1", raList, false)));
        assertEquals("adjacentFind should locate adjacent nulls too",
                2, ListHelper.adjacentFind(getList("1,2,N,N", raList, false)));
        assertEquals("adjacentFind should return -1 if none adjacent elements are equal",
                -1, ListHelper.adjacentFind(getList("0,1,2", raList, false)));
        assertEquals("adjacentFind should return -1 if none adjacent elements are equal",
                -1, ListHelper.adjacentFind(getList("0,1,0,1", raList, false)));
        assertEquals("adjacentFind should return -1 if none adjacent elements are equal",
                -1, ListHelper.adjacentFind(getList("N,1,N,3", raList, false)));

        //now do some testing for sublists too
        assertEquals("adjacentFind should return -1 even if the sublist is empty",
                -1, ListHelper.adjacentFind(getList("0,1,2", raList, false).subList(1, 1)));
        assertEquals("adjacentFind should return -1 even if the sublist is of size one",
                -1, ListHelper.adjacentFind(getList("0,1,2", raList, false).subList(1, 2)));
        assertEquals("adjacentFind should return -1 even if the sublist is of size one",
                -1, ListHelper.adjacentFind(getList("0,0,0", raList, false).subList(1, 2)));
        assertEquals("adjacentFind should limit search within the sublist",
                -1, ListHelper.adjacentFind(getList("0,0,1,2", raList, false).subList(1, 4)));
        assertEquals("adjacentFind should locate adjacent values in sublist too",
                0, ListHelper.adjacentFind(getList("0,0,0,2", raList, false).subList(1, 4)));
        assertEquals("adjacentFind should limit search within the sublist",
                -1, ListHelper.adjacentFind(getList("N,N,1,2", raList, false).subList(1, 4)));
        assertEquals("adjacentFind should locate adjacent values in sublist too",
                0, ListHelper.adjacentFind(getList("N,N,N,2", raList, false).subList(1, 4)));
        assertEquals("adjacentFind should return -1 if none adjacent elements are equal",
                -1, ListHelper.adjacentFind(getList("0,1,2,3,4", raList, false).subList(1, 4)));
        assertEquals("adjacentFind should return -1 if none adjacent elements are equal",
                -1, ListHelper.adjacentFind(getList("N,1,N,3,N", raList, false).subList(1, 4)));
    }

    public void testFindFirstOf()
    {
        findFirstOfTestEmpty();
        findFirstOfTest(true);
        findFirstOfTest(false);
    }

    private static void findFirstOfTest(final boolean raList)
    {
        assertEquals("findFirstOf should return -1 if the data is disjoint",
                -1, ListHelper.findFirstOf(getList("1,2,3", raList, false), getList("4,5,6", raList, false)));
        assertEquals("findFirstOf should return -1 if the data is disjoint",
                -1, ListHelper.findFirstOf(getList("1,2,3", raList, false), getList("N,N", raList, false)));
        assertEquals("findFirstOf should locate the first common element",
                1, ListHelper.findFirstOf(getList("1,2,3", raList, false), getList("2,2,3", raList, false)));
        assertEquals("findFirstOf should locate the first common element",
                0, ListHelper.findFirstOf(getList("1,2,3", raList, false), getList("2,1", raList, false)));
        assertEquals("findFirstOf should locate the first common element",
                0, ListHelper.findFirstOf(getList("1,2,3", raList, false), getList("1,2", raList, false)));
        assertEquals("findFirstOf should locate the first common element even null",
                2, ListHelper.findFirstOf(getList("1,2,N", raList, false), getList("0,N", raList, false)));
        //check that this logic works even if the sublists overlap
        final List list1 = getList("1,2,3,4,2,3,4,5,6,7", raList, false);
        assertEquals("findFirstOf should locate the first common element even if sublist overlap",
                1, ListHelper.findFirstOf(list1.subList(0, 4), list1.subList(4, 7)));
        assertEquals("findFirstOf should locate the first common element even if sublist overlap",
                0, ListHelper.findFirstOf(list1.subList(4, 7), list1.subList(0, 4)));
        assertEquals("findFirstOf should return -1 if sublists are disjoint",
                -1, ListHelper.findFirstOf(list1.subList(4, 7), list1.subList(7, 10)));
    }

    private static void findFirstOfTestEmpty()
    {
        assertEquals("findFirstOf should return -1 if either list is null",
                -1, ListHelper.findFirstOf(null, Collections.EMPTY_LIST));
        assertEquals("findFirstOf should return -1 if either list is null",
                -1, ListHelper.findFirstOf(Collections.EMPTY_LIST, null));
        assertEquals("findFirstOf should return -1 if either list is null",
                -1, ListHelper.findFirstOf(null, null));
        assertEquals("findFirstOf should return -1 if either list is null",
                -1, ListHelper.findFirstOf(null, getList("1,2,3", true, false)));
        assertEquals("findFirstOf should return -1 if either list is null",
                -1, ListHelper.findFirstOf(getList("1,2,3", true, false), null));
        assertEquals("findFirstOf should return -1 if either list is empty",
                -1, ListHelper.findFirstOf(Collections.EMPTY_LIST, Collections.EMPTY_LIST));
        assertEquals("findFirstOf should return -1 if either list is empty",
                -1, ListHelper.findFirstOf(getList("1,2,3", true, false), Collections.EMPTY_LIST));
        assertEquals("findFirstOf should return -1 if either list is empty",
                -1, ListHelper.findFirstOf(Collections.EMPTY_LIST, getList("1,2,3", true, false)));
    }

    public void testCount()
    {
        countTestEmpty();

        countTest(true);
        countTest(false);
    }

    private static void countTest(final boolean raList)
    {
        assertEquals("count should count correct number of elements",
                7, ListHelper.count(getList("0,1,2,1,3,1,1,5,1,1,1,8", raList, false), ONE));
        assertEquals("count should count correct number of nulls too",
                7, ListHelper.count(getList("0,N,2,N,3,N,N,5,N,N,N,8", raList, false), null));
        assertEquals("count should return zero if none match",
                0, ListHelper.count(getList("0,N,2,N,3,N,N,5,N,N,N,8", raList, false), ONE));
        assertEquals("count should return zero if no null match",
                0, ListHelper.count(getList("0,1,2,1,3,1,1,5,1,1,1,8", raList, false), null));

        //test for sublist
        assertEquals("count should return 0 if the list is empty",
                0, ListHelper.count(getList("0,1,2,1,3,1,1,5,1,1,1,8", raList, false).subList(3, 3), ZERO));
        assertEquals("count should return 0 if the list is empty",
                0, ListHelper.count(getList("0,1,2,1,3,1,1,5,1,1,1,8", raList, false).subList(3, 3), null));
        assertEquals("count should count correct number of elements in sublist",
                2, ListHelper.count(getList("0,1,2,1,3,1,1,5,1,1,1,8", raList, false).subList(2, 6), ONE));
        assertEquals("count should count correct number of nulls too in sublist",
                2, ListHelper.count(getList("0,N,2,N,3,N,N,5,N,N,N,8", raList, false).subList(2, 6), null));
        assertEquals("count should return zero if none match in sublist",
                0, ListHelper.count(getList("0,1,2,N,3,N,N,5,1,1,1,8", raList, false).subList(2, 6), ONE));
        assertEquals("count should return zero if no null match in sublist",
                0, ListHelper.count(getList("0,N,2,1,3,1,1,5,N,N,N,8", raList, false).subList(2, 6), null));
    }

    private static void countTestEmpty()
    {
        assertEquals("count should return 0 if the list is null",
                0, ListHelper.count(null, ZERO));
        assertEquals("count should return 0 if the list is null",
                0, ListHelper.count(null, null));
        assertEquals("count should return 0 if the list is empty",
                0, ListHelper.count(Collections.EMPTY_LIST, ZERO));
        assertEquals("count should return 0 if the list is empty",
                0, ListHelper.count(Collections.EMPTY_LIST, null));
    }

    public void testMismatch()
    {
        mismatchTestEmpty();

        mismatchTest(true);
        mismatchTest(false);
    }

    private static void mismatchTest(final boolean raList)
    {
        assertEquals("equal lists should match and return -1",
                mismatchTestReflexive(getList("1,2,3", raList, false), getList("1,2,3", raList, false)), -1);
        final List list1 = getList("1,2,3,4,1,2,3,5", raList, false);
        assertEquals("equal sub lists should match and return -1",
                mismatchTestReflexive(list1.subList(0, 3), list1.subList(4, 7)), -1);
        final List list2 = getList("3,2,3,2,3,2,4", raList, false);
        assertEquals("equal overlapping sublists should match and return -1",
                mismatchTestReflexive(list2.subList(1, 4), list2.subList(3, 6)), -1);
        assertEquals("unequal same sized list should mismatch",
                1, mismatchTestReflexive(getList("1,2,3", raList, false), getList("1,N,3", raList, false)));
        assertEquals("unequal starting list of different size should mismatch",
                2, mismatchTestReflexive(getList("1,2,3", raList, false), getList("1,2,4,5,5", raList, false)));
        assertEquals("equal starting list of differnt size should mismatch",
                3, mismatchTestReflexive(getList("N,2,3", raList, false), getList("N,2,3,4", raList, false)));
    }

    private static void mismatchTestEmpty()
    {
        assertEquals("null lists should match and return -1",
                mismatchTestReflexive(null, null), -1);
        assertEquals("empty lists should match and return -1",
                mismatchTestReflexive(Collections.EMPTY_LIST, Collections.EMPTY_LIST), -1);
        assertEquals("empty list and null should also match and return -1",
                mismatchTestReflexive(Collections.EMPTY_LIST, null), -1);
        assertEquals("empty list and non empty list should mismatch and return 0",
                0, mismatchTestReflexive(Collections.EMPTY_LIST, getList("1,2,3", true, false)));
        assertEquals("non empty list and null should mismatch and return 0",
                0, mismatchTestReflexive(getList("1,2,3", true, false), null));
    }

    private static <T> int mismatchTestReflexive(final List<T> list1, final List<T> list2)
    {
        final int value1 = ListHelper.mismatch(list1, list2);
        final int value2 = ListHelper.mismatch(list2, list1);
        assertEquals("mismatch result should be reflexive", value1, value2);
        return value1;
    }

    public void testEqual()
    {
        equalTestEmpty();
        //TODO other non empty tests
    }

    private static void equalTestEmpty()
    {
        assertTrue("null lists should be equal", equalTestReflexive(null, null));
        assertTrue("null and not null list should be unequal",
                !equalTestReflexive(null, getList("1,2,3", true, false)));
        assertTrue("empty lists should be equal", equalTestReflexive(Collections.EMPTY_LIST, Collections.EMPTY_LIST));
    }

    @SuppressWarnings({"BooleanMethodNameMustStartWithQuestion"})
    private static <T> boolean equalTestReflexive(final List<T> list1, final List<T> list2)
    {
        final boolean value1 = ListHelper.equal(list1, list2);
        final boolean value2 = ListHelper.equal(list2, list1);
        assertEquals("equal result should be reflexive", value1, value2);
        return value1;
    }

    public void testSearch()
    {
        searchTestEmpty();

        searchTest(true);
        searchTest(false);
    }

    private static void searchTest(final boolean raList)
    {
        //TODO add test cases for null elements
        assertEquals("searching for single element list should work",
                1, ListHelper.search(getList("1,2,2,3,3", raList, false), getList("2", raList, false)));
        assertEquals("searching for single element list should fail if not present",
                -1, ListHelper.search(getList("1,2,4,5,6", raList, false), getList("3", raList, false)));
        assertEquals("searching for a list should work",
                2, ListHelper.search(getList("1,2,3,2,3,2,3,4", raList, false), getList("3,2", raList, false)));
        assertEquals("searching in sublist should also work",
                1, ListHelper.search(getList("1,2,3,2,3,2,3,4", raList, false).subList(3, 7),
                getList("3,2", raList, false)));
        assertEquals("searching should fail if list is not there",
                -1, ListHelper.search(getList("1,2,3,4,5", raList, false), getList("2,1", raList, false)));
        assertEquals("searching should work",
                4, ListHelper.search(getList("1,2,3,4,2,3,4,5,2", raList, false), getList("2,3,4,5", raList, false)));
    }

    private static void searchTestEmpty()
    {
        assertEquals("null list should return -1 on search",
                -1, ListHelper.search(null, getList("1,2", true, false)));
        assertEquals("null list should return -1 on search",
                -1, ListHelper.search(null, null));
        assertEquals("searching for null list should return -1",
                -1, ListHelper.search(getList("1,2,3", true, false), null));
        assertEquals("empty list should return -1 on search",
                -1, ListHelper.search(Collections.EMPTY_LIST, getList("1,2", true, false)));
        assertEquals("empty list should return -1 on search",
                -1, ListHelper.search(Collections.EMPTY_LIST, null));
        assertEquals("searching for empty list should return -1",
                -1, ListHelper.search(getList("1,2,3", true, false), Collections.EMPTY_LIST));
    }

    public void testSearchN()
    {
        searchNTestEmpty();

        searchNTest(true);
        searchNTest(false);
    }

    private static void searchNTest(final boolean raList)
    {
        assertEquals("searchN should work",
                5, ListHelper.searchN(getList("1,2,2,2,3,2,2,2,2,2,N,1", raList, false), 4, TWO));
        assertEquals("searchN should work at boundaries too",
                0, ListHelper.searchN(getList("1,1,1,2,1,1,1", raList, false), 3, ONE));
        assertEquals("searchN should work at boundaries too",
                3, ListHelper.searchN(getList("1,1,2,1,1,1", raList, false), 3, ONE));
        assertEquals("searchN should work on sublist too",
                2, ListHelper.searchN(getList("1,2,2,2,3,2,2,3", raList, false).subList(3, 7), 2, TWO));
        assertEquals("searchN should work for nulls too",
                5, ListHelper.searchN(getList("1,N,N,N,3,N,N,N,N,2,1", raList, false), 4, null));
        assertEquals("searchN should fail if no susbseq is found",
                -1, ListHelper.searchN(getList("1,2,3,4,5", raList, false), 2, TWO));
        assertEquals("searchN should fail if no subseq is found",
                -1, ListHelper.searchN(getList("N,N,1,N,2,N,N", raList, false), 3, null));
        assertEquals("searchN should work for one element too",
                0, ListHelper.searchN(getList("1,2,3,4", raList, false), 1, ONE));
        assertEquals("searchN should work for one element null too",
                3, ListHelper.searchN(getList("1,2,3,N", raList, false), 1, null));
        assertEquals("searchN should not fail if single element is not found",
                -1, ListHelper.searchN(getList("1,N,3,4,5", raList, false), 1, TWO));
        assertEquals("searchN should not fail if single element null is not found",
                -1, ListHelper.searchN(getList("1,2,3,4,5", raList, false), 1, null));
    }

    private static void searchNTestEmpty()
    {
        assertEquals("null list should return -1 on search",
                -1, ListHelper.searchN(null, 1, ZERO));
        assertEquals("null list should return -1 on search",
                -1, ListHelper.searchN(null, 2, null));
        assertEquals("empty list should return -1 on search",
                -1, ListHelper.searchN(Collections.EMPTY_LIST, 1, ZERO));
        assertEquals("empty list should return -1 on search",
                -1, ListHelper.searchN(Collections.EMPTY_LIST, 1, null));
        assertEquals("empty sublist should return -1 on search",
                -1, ListHelper.searchN(getList("1,2,3", true, false).subList(1, 1), 1, ONE));
    }

    public void testFindEnd()
    {
        findEndTestEmpty();

        findEndTest(true);
        findEndTest(false);
    }

    private static void findEndTest(final boolean raList)
    {
        assertEquals("findEnd should return -1 if size of list1 is less than size of list2",
                -1, ListHelper.findEnd(getList("1,2", raList, false), getList("1,2,3", raList, false)));
        assertEquals("findEnd should work for list2 of size 1",
                3, ListHelper.findEnd(getList("1,2,3,2,4", raList, false), getList("2", raList, false)));
        assertEquals("findEnd should work for list2 of size 1 for nulls too",
                3, ListHelper.findEnd(getList("1,N,2,N", raList, false), getList("N", raList, false)));
        assertEquals("findEnd should fail for list2 of size 1",
                -1, ListHelper.findEnd(getList("1,2,3", raList, false), getList("0", raList, false)));
        assertEquals("findEnd should fail for list2 of size 1 for nulls too",
                -1, ListHelper.findEnd(getList("1", raList, false), getList("N", raList, false)));
        assertEquals("findEnd should work",
                1, ListHelper.findEnd(getList("1,2,3,2,4,3", raList, false), getList("2,3", raList, false)));
        assertEquals("findEnd should work on boundaries too",
                0, ListHelper.findEnd(getList("1,2,3", raList, false), getList("1,2,3", raList, false)));
        assertEquals("findEnd should work on boundaries too",
                0, ListHelper.findEnd(getList("1,N,3,4", raList, false), getList("1,N,3", raList, false)));
        assertEquals("findEnd should work on boundaries too",
                1, ListHelper.findEnd(getList("1,2,3,N", raList, false), getList("2,3,N", raList, false)));
        assertEquals("findEnd should work even if there are many almost matches",
                0, ListHelper.findEnd(getList("1,2,3,2,3,1,2,4,3,N,1,3,2,3", raList, false),
                getList("1,2,3", raList, false)));
        assertEquals("findEnd should fail if list not found",
                -1, ListHelper.findEnd(getList("1,2,3", raList, false), getList("1,3", raList, false)));
        assertEquals("findEnd should fail if list not found",
                -1, ListHelper.findEnd(getList("1,2,3", raList, false), getList("N,3", raList, false)));
        assertEquals("findEnd should work for sublists too",
                0, ListHelper.findEnd(getList("1,2,3,1,2,3", raList, false).subList(0, 5),
                getList("1,2,3", raList, false)));
        assertEquals("findEnd should fail for sublists too",
                ListHelper.findEnd(getList("1,2,3,1,2,3", raList, false).subList(1, 5),
                        getList("1,2,3", raList, false)), -1);
    }

    private static void findEndTestEmpty()
    {
        assertEquals("findEnd should return -1 if either list is null",
                -1, ListHelper.findEnd(null, null));
        assertEquals("findEnd should return -1 if either list is null",
                -1, ListHelper.findEnd(null, Collections.EMPTY_LIST));
        assertEquals("findEnd should return -1 if either list is null",
                -1, ListHelper.findEnd(getList("1,2,3", true, false), null));
        assertEquals("findEnd should return -1 if either list is of size 1",
                -1, ListHelper.findEnd(Collections.EMPTY_LIST, Collections.EMPTY_LIST));
        assertEquals("findEnd should return -1 if either list is of size 1",
                -1, ListHelper.findEnd(Collections.EMPTY_LIST, getList("1,2,3", true, false)));
        assertEquals("findEnd should return -1 if either list is of size 1",
                -1, ListHelper.findEnd(getList("1,2,3", true, false), Collections.EMPTY_LIST));
    }

    public void testUnique()
    {
        uniqueTestEmpty();
        uniqueTest(true);
        uniqueTest(false);
    }

    private static void uniqueTest(final boolean raList)
    {
        assertFalse("unique should return false if the list is of size 1",
                ListHelper.unique(getList("1", raList, false)));
        assertFalse("unique should return false if the list is of size 1",
                ListHelper.unique(getList("N", raList, false)));
        assertFalse("unique should return false if the list is of size 1",
                ListHelper.unique(getList("1", raList, false)));
        assertTrue("unique should return false if all elements are unique",
                !ListHelper.unique(getList("1,2,3,4,5,N", raList, true)));
        assertTrue("unique should return false if no consecutive elements are same",
                !ListHelper.unique(getList("1,2,1,2,1,2", raList, true)));
        List list1 = getList("1,2,2,1,1,3,3,3,3,N,N,2,2,5", raList, true);
        List list2 = getList("1,2,1,3,N,2,5", raList, false);
        assertTrue("unique should work",
                ListHelper.unique(list1) && list1.equals(list2));
        list1 = getList("N,N,N,N", raList, true);
        list2 = getList("N", raList, false);
        assertTrue("unique should work even if all are the same element",
                ListHelper.unique(list1) && list1.equals(list2));
        list1 = getList("5,5,4,4,3,3,2,1", raList, true);
        list2 = getList("5,4,3,2,1", raList, false);
        assertTrue("unique should work and ordering should remain same",
                ListHelper.unique(list1) && list1.equals(list2));
        list1 = getList("1,1,1,2,1,1,1,3,1,1,1,1", raList, true);
        list2 = getList("1,2,1,3,1", raList, false);
        assertTrue("unique should work on boundaries too",
                ListHelper.unique(list1) && list1.equals(list2));
        list1 = getList("1,1,1,1,2,2,3,3,3,", raList, true);
        list2 = getList("1,1,1,2,3,3", raList, false);
        assertTrue("unique should work for sublists too",
                ListHelper.unique(list1.subList(2, 8)) && list1.equals(list2));
        assertTrue("unique should return unaltered sublist if already unique",
                !ListHelper.unique(list2.subList(2, 5)));

        uniqueTestRandom(raList);
    }

    private static void uniqueTestRandom(final boolean raList)
    {
        for (int i = 0; i < 100; i++)
        {
            final List list1 = getRandomList(raList);
            final List list2 = cloneList(list1, false);
            final int afResult = ListHelper.adjacentFind(list1);
            final boolean uniqueResult = ListHelper.unique(list1);
            if (afResult == -1)
            {
                assertTrue("unique should return false if adjacentFind returns -1"
                        + listsInTest(list1, list2), !uniqueResult);
                assertTrue("unique should not have changed the list if it returns false"
                        + listsInTest(list1, list2), list1.equals(list2));
            }
            else
            {
                assertTrue("unique should return true if adjacentFind returns something"
                        + listsInTest(list1, list2), uniqueResult);
                assertTrue("unique should have changed the list if it returns true"
                        + listsInTest(list1, list2),
                        !list1.equals(list2) && list1.size() < list2.size());
            }
        }
    }

    private static void uniqueTestEmpty()
    {
        assertFalse("unique should return false if the list is empty",
                ListHelper.unique(null));
        assertFalse("unique should return false if the list is null",
                ListHelper.unique(Collections.EMPTY_LIST));
    }

    public void testRemove()
    {
        removeTestEmpty();

        removeTest(true);
        removeTest(false);
    }

    private static void removeTestEmpty()
    {
        assertFalse("remove should return false for null",
                ListHelper.remove(null, ONE) || ListHelper.remove(null, null));
        assertFalse("remove should return false for empty list",
                ListHelper.remove(Collections.EMPTY_LIST, ONE)
                        || ListHelper.remove(Collections.EMPTY_LIST, null));
    }

    private static void removeTest(final boolean raList)
    {
        List list1;
        List list2;
        list1 = getList("1,2,3,4,5", raList, true);
        list2 = cloneList(list1, false);
        assertTrue("remove should return false if element not found",
                !ListHelper.remove(list1, ZERO));
        assertTrue("if nothing is removed the list should remain the same", list1.equals(list2));
        assertTrue("remove should true if something is removed", ListHelper.remove(list1, ONE));
        assertTrue("if something is removed then the list should change", !list1.equals(list2));
        list2 = getList("2,3,4,5", raList, false);
        assertTrue("remove should work", list1.equals(list2));
        assertTrue("remove should work for nulls", !ListHelper.remove(list1, null));
        list1 = getList("1,N,2,N,3", raList, true);
        list2 = getList("1,2,3", raList, false);
        assertTrue("remove should work for nulls too",
                ListHelper.remove(list1, null) && list1.equals(list2));
        list1 = getList("1,1,1,1,1", raList, true);
        assertTrue("remove should work for list containing same element",
                ListHelper.remove(list1, ONE) && Collections.EMPTY_LIST.equals(list1));
        list1 = getList("1,1,1,2,2,3,4", raList, true);
        list2 = getList("1,2,2,3,4", raList, false);
        assertTrue("remove should return unaltered sublist if element not found",
                !ListHelper.remove(list1.subList(1, 5), ZERO));
        assertTrue("remove should work for sublists too",
                ListHelper.remove(list1.subList(1, 5), ONE) && list1.equals(list2));
        list1 = getList("0", raList, true);
        assertTrue("remove should work on singleton list too",
                ListHelper.remove(list1, ZERO) && list1.equals(Collections.EMPTY_LIST));
    }

    public void testReplace()
    {
        replaceTestEmpty();
        replaceTest(true);
        replaceTest(false);
    }

    private static void replaceTest(final boolean raList)
    {
        List list1;
        List list2;
        list1 = getList("1,2,3,1,2,1", raList, true);
        list2 = cloneList(list1, false);
        assertTrue("replace should work for identical objects too",
                ListHelper.replace(list1, ONE, ONE) && list1.equals(list2));
        assertTrue("replace should work for identical objects too",
                !ListHelper.replace(list1, ZERO, ZERO));
        list2 = getList("2,2,3,2,2,2", raList, false);
        assertTrue("replace should work",
                ListHelper.replace(list1, ONE, TWO) && list1.equals(list2));
        assertTrue("replace should return unaltered list if list doesnot contain the element",
                !ListHelper.replace(list1, ONE, TWO) && list1.equals(list2));
        list1 = getList("N,2,3,N,2,N", raList, true);
        list2 = cloneList(list1, false);
        assertTrue("replace should work for identical objects too",
                ListHelper.replace(list1, null, null) && list1.equals(list2));
        list1 = getList("1,2,N,3,N,4", raList, true);
        list2 = getList("1,2,0,3,0,4", raList, false);
        assertTrue("replace should work for nulls too",
                ListHelper.replace(list1, null, ZERO) && list1.equals(list2));
        list2 = getList("1,2,N,3,N,4", raList, false);
        assertTrue("replace should work even if replacement is null",
                ListHelper.replace(list1, ZERO, null) && list1.equals(list2));
        list1 = getList("1,N,N,N,2,N,N,N,3", raList, true);
        list2 = getList("1,N,N,0,2,0,0,N,3", raList, false);
        assertTrue("replace should work for sublists too",
                ListHelper.replace(list1.subList(3, 7), null, ZERO) && list1.equals(list2));
        replaceTestRandom(raList);
    }

    private static void replaceTestRandom(final boolean raList)
    {
        for (int i = 0; i < 100; i++)
        {
            final List list1 = getRandomList(raList);
            final int originalSize = list1.size();
            final boolean elementFound = ListHelper.find(list1, ONE) != -1;
            assertTrue("replace should return true iff the element was found in the list",
                    xor(ListHelper.replace(list1, ONE, TWO), !elementFound));
            assertEquals("size of the list should remain unchanged", originalSize, list1.size());
            assertTrue("replace should return false if called twice on the same list with same params",
                    !ListHelper.replace(list1, ONE, TWO));
        }
    }

    private static void replaceTestEmpty()
    {
        assertFalse("replace should return false for null list",
                ListHelper.replace(null, ONE, TWO));
        assertFalse("replace should return false for empty list",
                ListHelper.replace(Collections.EMPTY_LIST, ONE, TWO));
    }

    public void testIsSorted()
    {
        isSortedTestEmpty();
        isSortedTest(true);
        isSortedTest(false);
    }

    @SuppressWarnings({"NonBooleanMethodNameMayNotStartWithQuestion"})
    private static void isSortedTest(final boolean raList)
    {
        assertTrue("isSorted should return true for list with one element",
                ListHelper.isSorted(getList("1", raList, false)));
        assertTrue("isSorted should return true for sorted list",
                ListHelper.isSorted(getList("1,2,3", raList, false)));
        assertTrue("isSorted should return true for sorted list with duplicate elememts",
                ListHelper.isSorted(getList("1,1,2,3", raList, false)));
        assertTrue("isSorted should return true for sorted list with duplicate elememts",
                ListHelper.isSorted(getList("1,1,1", raList, false)));
        assertFalse("isSorted should return false for unsorted list",
                ListHelper.isSorted(getList("1,1,3,2", raList, false)));
        assertFalse("isSorted should return false for unsorted list",
                ListHelper.isSorted(getList("4,3,2", raList, false)));
        assertTrue("isSorted should return true for sorted list with nulls",
                ListHelper.isSorted(getList("N,1,2", raList, false)));
        assertTrue("isSorted should return true for sorted list with nulls",
                ListHelper.isSorted(getList("N,N,N", raList, false)));
        assertFalse("isSorted should return false for unsorted list with nulls",
                ListHelper.isSorted(getList("N,1,N", raList, false)));
        assertFalse("isSorted should return false for unsorted list with nulls",
                ListHelper.isSorted(getList("1,N,2", raList, false)));
        assertFalse("isSorted should return false for unsorted list with nulls",
                ListHelper.isSorted(getList("1,2,N", raList, false)));

        for (int i = 0; i < 200; i++)
        {
            final List<Integer> list1 = getRandomList(raList);
            final List<Integer> list2 = cloneList(list1, false);
            ListHelper.sort(list1);
            assertTrue("either the random list was already sorted or the sorting made some difference"
                    + ": using list : " + listsInTest(list2),
                    ListHelper.isSorted(list2) || !list2.equals(list1));
        }
    }

    @SuppressWarnings({"NonBooleanMethodNameMayNotStartWithQuestion"})
    private static void isSortedTestEmpty()
    {
        final List<Integer> list = null;
        assertTrue("isSorted should return true for null list",
                ListHelper.isSorted(list));
        assertTrue("isSorted should return true for empty list",
                ListHelper.isSorted(Collections.EMPTY_LIST));
    }

    public void testSetUnion()
    {
        setUnionTestEmpty();
        setUnionTest(true);
        setUnionTest(false);
    }


    private static void setUnionTestEmpty()
    {
        List list1;
        final List list2;
        List list3;
        list1 = new ArrayList(1);
        assertTrue("setUnion should work with empty list too",
                !ListHelper.setUnion(list1, Collections.EMPTY_LIST) && list1.equals(Collections.EMPTY_LIST));
        assertTrue("setUnion should work with null list too",
                !ListHelper.setUnion(list1, null) && list1.equals(Collections.EMPTY_LIST));
        list1 = new ArrayList(1);
        list2 = getList("1,1,2,2,2", true, false);
        assertTrue("setUnion should work with empty list too for multiple items",
                ListHelper.setUnion(list1, list2) && list1.equals(list2));
    }

    private static void setUnionTest(final boolean raList)
    {
        List list1;
        List list2;
        List list3;
        list1 = new ArrayList(1);
        list2 = getList("1", raList, false);
        assertTrue("setUnion should work with empty list too",
                ListHelper.setUnion(list1, list2) && list1.equals(list2));
        list1 = getList("1", raList, true);
        list2 = getList("2", raList, false);
        list3 = getList("1,2", raList, false);
        assertTrue("setUnion should work for single element too",
                ListHelper.setUnion(list1, list2) && list1.equals(list3));
        list1 = getList("1,2,4,5", raList, true);
        list2 = getList("2,3,6", raList, false);
        list3 = getList("1,2,3,4,5,6", raList, false);
        assertTrue("setUnion should work",
                ListHelper.setUnion(list1, list2) && list1.equals(list3));
        list1 = getList("1,2,4", raList, true);
        list2 = getList("3", raList, false);
        list3 = getList("1,2,3,4", raList, false);
        assertTrue("setUnion should work",
                ListHelper.setUnion(list1, list2) && list1.equals(list3));
        list1 = getList("2,5,7,8", raList, true);
        list2 = getList("0,1,2,4,8", raList, false);
        list3 = getList("0,1,2,4,5,7,8", raList, false);
        assertTrue("setUnion should work",
                ListHelper.setUnion(list1, list2) && list1.equals(list3));
        list1 = getList("1,2,4", raList, true);
        list2 = getList("0", raList, false);
        list3 = getList("0,1,2,4", raList, false);
        assertTrue("setUnion should work at boundary too",
                ListHelper.setUnion(list1, list2) && list1.equals(list3));
        list1 = getList("1,2,3", raList, true);
        list2 = getList("2,2", raList, false);
        list3 = getList("1,2,2,3", raList, false);
        assertTrue("setUnion should work for multiple items",
                ListHelper.setUnion(list1, list2) && list1.equals(list3));
        list1 = getList("1,2,2,3", raList, true);
        list2 = getList("2", raList, false);
        list3 = getList("1,2,2,3", raList, false);
        assertTrue("setUnion should work for multiple items",
                !ListHelper.setUnion(list1, list2) && list1.equals(list3));
        list1 = getList("1,2,4", raList, true);
        list2 = getList("3,3", raList, false);
        list3 = getList("1,2,3,3,4", raList, false);
        assertTrue("setUnion should work for multiple items",
                ListHelper.setUnion(list1, list2) && list1.equals(list3));
        list1 = getList("1,1,1", raList, true);
        list2 = getList("1,1", raList, false);
        list3 = getList("1,1,1", raList, false);
        assertTrue("setUnion should work for multiple same items",
                !ListHelper.setUnion(list1, list2) && list1.equals(list3));
        list1 = getList("1,1", raList, true);
        list2 = getList("1,1,1,1", raList, false);
        list3 = getList("1,1,1,1", raList, false);
        assertTrue("setUnion should work for multiple same items",
                ListHelper.setUnion(list1, list2) && list1.equals(list3));
        list1 = getList("1,3,3,5,5,5,6", raList, false);
        assertTrue("setUnion with oneself should return false",
                !ListHelper.setUnion(list1, list1));
        list1 = getList("1,1,1,1", raList, true);
        list2 = getList("1,1,1,1", raList, false);
        list3 = getList("1,1,1,1,1,1", raList, false);
        assertTrue("setUnion should work for sublists too",
                ListHelper.setUnion(list1.subList(1, 3), list2) && list1.equals(list3));
        list1 = getList("1,2,3,4", raList, true);
        list2 = getList("1,4", raList, false);
        list3 = getList("1,1,2,3,4,4,", raList, false);
        assertTrue("setUnion should work for sublists too",
                ListHelper.setUnion(list1.subList(1, 3), list2) && list1.equals(list3));
        setUnionTestRandom(raList);
    }

    private static void setUnionTestRandom(final boolean raList)
    {
        List list1;
        List list2;
        List list3;
        for (int i = 0; i < 100; i++)
        {
            list1 = getRandomSortedList(raList, true);
            list2 = getRandomSortedList(raList, true);
            ListHelper.unique(list1);
            ListHelper.unique(list2);
            list3 = cloneList(list1, true);
            list3.addAll(list2);
            ListHelper.sort(list3);
            ListHelper.unique(list3);
            final List list4 = cloneList(list1, false);
            final List list5 = cloneList(list2, false);
            ListHelper.setUnion(list1, list2);
            assertTrue("uniq(sort(anylist1)) union uniq(sort(anylist2)) == uniq(sort(anylist1 + anylist2)) "
                    + listsInTest(list4, list5), list1.equals(list3));
        }
        for (int i = 0; i < 100; i++)
        {
            list1 = getRandomSortedList(raList, true);
            list2 = getRandomSortedList(raList, true);
            list3 = cloneList(list1, false);
            final List list4 = cloneList(list2, false);
            ListHelper.setUnion(list1, list4);
            ListHelper.setUnion(list2, list3);
            assertTrue("setUnion should be reflexive " + listsInTest(list3, list4),
                    list1.equals(list2));
        }
        for (int i = 0; i < 100; i++)
        {
            list1 = getRandomSortedList(raList, false);
            assertTrue("setUnion with oneself should return false" + listsInTest(list1),
                    !ListHelper.setUnion(list1, list1));
        }
        for (int i = 0; i < 100; i++)
        {
            list1 = getRandomSortedList(raList, true);
            list2 = getRandomSortedList(raList, false);
            list3 = cloneList(list1, false);
            ListHelper.setUnion(list1, list2);
            assertTrue("list1 should remain sorted after setUnion " + listsInTest(list3, list2),
                    ListHelper.isSorted(list1));
        }
    }

    public void testSetIntersection()
    {
        setIntersectionTestEmpty();
        setIntersectionTest(true);
        setIntersectionTest(false);
    }

    private static void setIntersectionTest(final boolean raList)
    {
        List list1;
        List list2;
        List list3;
        list1 = getList("1,2", raList, true);
        list2 = getList("2", raList, false);
        assertTrue("setIntersection should work for single element too",
                ListHelper.setIntersection(list1, list2) && list1.equals(list2));
        list1 = getList("1,2,3,4,5,7", raList, true);
        list2 = getList("0,2,4,6", raList, false);
        list3 = getList("2,4", raList, false);
        assertTrue("setIntersection should work",
                ListHelper.setIntersection(list1, list2) && list1.equals(list3));
        list1 = getList("1,3,5,7", raList, true);
        list2 = getList("2,4,6,8", raList, false);
        assertTrue("setIntersection should work for disjoint lists",
                ListHelper.setIntersection(list1, list2) && list1.equals(Collections.EMPTY_LIST));
        list1 = getList("1,2,3", raList, true);
        list2 = getList("1,3", raList, false);
        assertTrue("setIntersection should work at boundaries too",
                ListHelper.setIntersection(list1, list2) && list1.equals(list2));
        list1 = getList("1,1,2,2,2,3,4,5", raList, true);
        list2 = getList("0,1,2,2,2,2,4,7", raList, false);
        list3 = getList("1,2,2,2,4", raList, false);
        assertTrue("setIntersection should work for multiple elements too",
                ListHelper.setIntersection(list1, list2) && list1.equals(list3));
        list1 = getList("1,2,2,2,4,4,8", raList, true);
        list2 = getList("0,0,0", raList, false);
        assertTrue("setIntersection should work for disjoint multiple elements too",
                ListHelper.setIntersection(list1, list2) && list1.equals(Collections.EMPTY_LIST));
        list1 = getList("1,1,1,1", raList, true);
        list2 = getList("1,1", raList, false);
        assertTrue("setIntersection should work for sublists too",
                !ListHelper.setIntersection(list1.subList(1, 3), list2));
        list1 = getList("1,1,1,1", raList, true);
        list2 = getList("1,1", raList, false);
        list3 = getList("1,1,1", raList, false);
        assertTrue("setIntersection should work for sublists too",
                ListHelper.setIntersection(list1.subList(1, 4), list2) && list1.equals(list3));
        setIntersectionTestRandom(raList);
    }

    private static void setIntersectionTestRandom(final boolean raList)
    {
        List list1;
        List list2;
        List list3;
        for (int i = 0; i < 100; i++)
        {
            list1 = getRandomSortedList(raList, true);
            list2 = getRandomSortedList(raList, true);
            list3 = cloneList(list1, false);
            final List list4 = cloneList(list2, false);
            ListHelper.setIntersection(list1, list4);
            ListHelper.setIntersection(list2, list3);
            assertTrue("setIntersection should be reflexive " + listsInTest(list3, list4),
                    list1.equals(list2));
        }
        for (int i = 0; i < 100; i++)
        {
            list1 = getRandomSortedList(raList, true);
            list2 = getRandomSortedList(raList, false);
            ListHelper.unique(list1);
            list3 = cloneList(list1, true);
            list3.retainAll(list2);
            ListHelper.sort(list3);
            final List list4 = cloneList(list1, false);
            ListHelper.setIntersection(list1, list2);
            assertTrue("setIntersection should work similar to List.retainAll() for uniq lists "
                    + listsInTest(list4, list2), list1.equals(list3));
            assertTrue("list1 should remain sorted after setIntersection "
                    + listsInTest(list4, list2), ListHelper.isSorted(list1));
        }
    }

    private static void setIntersectionTestEmpty()
    {
        List list1;
        list1 = new ArrayList(1);
        assertTrue("setIntersection should work for empty list too",
                !ListHelper.setIntersection(list1, Collections.EMPTY_LIST) && list1.equals(Collections.EMPTY_LIST));
        assertTrue("setIntersection should work for null list too",
                !ListHelper.setIntersection(list1, null) && list1.equals(Collections.EMPTY_LIST));
        list1 = getList("1,2,2", true, true);
        assertTrue("setIntersection should work for empty list too",
                ListHelper.setIntersection(list1, Collections.EMPTY_LIST) && list1.equals(Collections.EMPTY_LIST));
        list1 = getList("1,2,2", true, true);
        assertTrue("setIntersection should work for null list too",
                ListHelper.setIntersection(list1, null) && list1.equals(Collections.EMPTY_LIST));
    }

    public void testSetDifference()
    {
        setDifferenceTestEmpty();
        setDifferenceTest(true);
        setDifferenceTest(false);
    }

    private static void setDifferenceTest(final boolean raList)
    {
        List list1;
        List list2;
        List list3;
        list1 = getList("1,2,3", raList, true);
        list2 = getList("2,3,4", raList, false);
        list3 = getList("1", raList, false);
        assertTrue("setDifference should work",
                ListHelper.setDifference(list1, list2) && list3.equals(list1));
        list1 = getList("1,2,3,5", raList, true);
        list2 = getList("1,3,4", raList, false);
        list3 = getList("2,5", raList, false);
        assertTrue("setDifference should work",
                ListHelper.setDifference(list1, list2) && list3.equals(list1));
        list1 = getList("1,2,3", raList, true);
//		list2 = cloneList(list1, false);
        assertTrue("setDifference with the same list should work",
                ListHelper.setDifference(list1, list1) && Collections.EMPTY_LIST.equals(list1));

        setDifferenceTestRandom(raList);
    }

    private static void setDifferenceTestRandom(final boolean raList)
    {
        List list1;
        List list2;
        List list3;
        List list4;
        for (int i = 0; i < 100; i++)
        {
            list1 = getRandomSortedList(raList, true);
            list2 = getRandomSortedList(raList, false);
            list3 = cloneList(list1, true);
            list4 = cloneList(list1, false);
            //A = (A-B) v (A^B)
            ListHelper.setDifference(list1, list2);
            ListHelper.setIntersection(list3, list2);
            list1.addAll(list3);
            ListHelper.sort(list1);
            assertTrue("A = (A-B) + (A^B) " + listsInTest(list4, list2),
                    list1.equals(list4));
        }
        for (int i = 0; i < 100; i++)
        {
            list1 = getRandomSortedList(raList, true);
            list2 = getRandomSortedList(raList, true);
            ListHelper.unique(list1);
            ListHelper.unique(list2);
            list3 = cloneList(list1, false);
            list4 = cloneList(list2, false);
            //0 = (A-B) ^ B				for unique element
            ListHelper.setDifference(list1, list2);
            ListHelper.setIntersection(list1, list2);
            assertTrue("0 = (A-B) ^ B for unique element : " + listsInTest(list3, list4),
                    list1.equals(Collections.EMPTY_LIST));
        }
        for (int i = 0; i < 100; i++)
        {
            list1 = getRandomSortedList(raList, true);
            list2 = getRandomSortedList(raList, true);
            ListHelper.unique(list1);
            ListHelper.unique(list2);
            list3 = cloneList(list1, true);
            list4 = cloneList(list1, false);
            //A = (A-B) v (A^B)				for unique element
            ListHelper.setDifference(list1, list2);
            ListHelper.setIntersection(list3, list2);
            ListHelper.setUnion(list1, list3);
            assertTrue("A = (A-B) v (A^B) for unique element : " + listsInTest(list4, list2),
                    list1.equals(list4));
        }
        for (int i = 0; i < 100; i++)
        {
            list1 = getRandomSortedList(raList, true);
            list2 = getRandomSortedList(raList, true);
            ListHelper.unique(list1);
            ListHelper.unique(list2);
            //A-B = (A-B) - B				for unique element
            ListHelper.setDifference(list1, list2);
            list4 = cloneList(list1, false);
            ListHelper.setDifference(list1, list2);
            assertTrue("A-B = (A-B) - B	for unique element : " + listsInTest(list4, list2),
                    list1.equals(list4));
        }
    }

    private static void setDifferenceTestEmpty()
    {
        List list1;
        List list2;
        list1 = new ArrayList(0);
        list2 = getList("1,2,3", true, false);
        assertTrue("setDifference should work for empty first list",
                !ListHelper.setDifference(list1, list2) && Collections.EMPTY_LIST.equals(list1));
        list1 = getList("1,2,3", true, false);
        list2 = new ArrayList(0);
        assertTrue("setDifference should work for empty second list",
                !ListHelper.setDifference(list1, list2));
        assertTrue("setDifference should work for null second list",
                !ListHelper.setDifference(list1, null));
    }

    public void testSetSymmetricDifference()
    {
        setSymmetricDifferenceTestRandom(true);
        setSymmetricDifferenceTestRandom(false);
    }

    private static void setSymmetricDifferenceTestRandom(final boolean raList)
    {
        List list1;
        List list2;
        List list3;
        List list4;
        for (int i = 0; i < 200; i++)
        {
            list1 = getRandomSortedList(raList, true);
            list2 = getRandomSortedList(raList, true);
            list3 = cloneList(list1, false);
            list4 = cloneList(list2, false);
            ListHelper.setSymmetricDifference(list1, list2);
            ListHelper.setSymmetricDifference(list2, list3);
            assertTrue("setSymmetricDifference should be reflexcive : " + listsInTest(list3, list4),
                    list1.equals(list2));
        }
        for (int i = 0; i < 200; i++)
        {
            list1 = getRandomSortedList(raList, true);
            list2 = getRandomSortedList(raList, true);
            list3 = cloneList(list1, false);
            list4 = cloneList(list2, false);
            ListHelper.setDifference(list1, list2);
            ListHelper.setDifference(list2, list3);
            ListHelper.setUnion(list2, list1);
            list1 = cloneList(list3, true);
            ListHelper.setSymmetricDifference(list1, list4);
            assertTrue("setSymmetricDifference = A-B V B-A : " + listsInTest(list3, list4),
                    list1.equals(list2));
        }
    }

    public void testMerge()
    {
        mergeTestEmpty();
        mergeTest(true);
        mergeTest(false);
    }

    private static void mergeTest(final boolean raList)
    {
        List list1;
        List list2;
        List list3;
        List list4;
        list1 = getList("1,3,5", raList, true);
        list2 = getList("2,4", raList, false);
        ListHelper.merge(list1, list2);
        assertTrue("merge should work", getList("1,2,3,4,5", raList, false).equals(list1));
        list1 = getList("1,2,3", raList, true);
        list2 = getList("1,2,3", raList, false);
        ListHelper.merge(list1, list2);
        assertTrue("merge should work", getList("1,1,2,2,3,3", raList, false).equals(list1));
        list1 = getList("1,2,3", raList, true);
        list2 = getList("1,2", raList, false);
        ListHelper.merge(list1, list2);
        assertTrue("merge should work", getList("1,1,2,2,3", raList, false).equals(list1));
        list1 = getList("1,2", raList, true);
        list2 = getList("1,2,3", raList, false);
        ListHelper.merge(list1, list2);
        assertTrue("merge should work", getList("1,1,2,2,3", raList, false).equals(list1));
        list1 = getList("2,3", raList, true);
        list2 = getList("1,2,3", raList, false);
        ListHelper.merge(list1, list2);
        assertTrue("merge should work", getList("1,2,2,3,3", raList, false).equals(list1));
        list1 = getList("1,2,3", raList, true);
        list2 = getList("2,3", raList, false);
        ListHelper.merge(list1, list2);
        assertTrue("merge should work", getList("1,2,2,3,3", raList, false).equals(list1));
        list1 = getList("1,2,2,2,3,3", raList, true);
        list2 = getList("1,2,3,3,3", raList, false);
        ListHelper.merge(list1, list2);
        assertTrue("merge should work", getList("1,1,2,2,2,2,3,3,3,3,3", raList, false).equals(list1));
        mergeTestRandom(raList);
    }

    private static void mergeTestRandom(final boolean raList)
    {
        List list1;
        List list2;
        List list3;
        List list4;
        for (int i = 0; i < 200; i++)
        {
            list1 = getRandomSortedList(raList, true);
            list2 = getRandomSortedList(raList, false);
            list3 = cloneList(list1, false);
            list4 = cloneList(list1, true);
            list4.addAll(list2);
            ListHelper.sort(list4);
            ListHelper.merge(list1, list2);
            assertTrue("merge should work : " + listsInTest(list3, list2),
                    list1.equals(list4));
        }
    }

    private static void mergeTestEmpty()
    {
        List list1;
        final List list2;
        list1 = new ArrayList();
        try
        {
            ListHelper.merge(list1, null);
        }
        catch (Exception ignore)
        {
            assertTrue("merge should handle second param as null", false);
        }
        list1 = new ArrayList();
        list2 = getRandomSortedList(true, false);
        ListHelper.merge(list1, list2);
        assertTrue("merge should work for empty list too", list2.equals(list1));
    }


    public void testCopy()
    {
        copyTest(true);
        copyTest(false);
    }

    private static void copyTest(final boolean raList)
    {
        List list1;
        List list2;
        final List list3;
        list1 = getList("1,2,3", raList, false);
        list2 = getList("3,2,1", raList, true);
        ListHelper.copy(list1, list2);
        assertTrue("copy should work", list2.equals(list1));
        list2 = getList("3", raList, true);
        ListHelper.copy(list1, list2);
        assertTrue("copy should work", list2.equals(list1));
        list2 = getList("4,3,2,1,0", raList, true);
        list3 = getList("1,2,3,1,0", raList, false);
        ListHelper.copy(list1, list2);
        assertTrue("copy should work", list2.equals(list3));
        list1 = getList("1,2", raList, false);
        list2 = new ArrayList(3);
        list2.add(1);
        ListHelper.copy(list1, list2);
        assertTrue("copy should work", list2.equals(list1));
        list1 = getList("1,2,3,4,5,6", raList, true);
        list2 = getList("1,2,3,1,2,3", raList, false);
        ListHelper.copy(list1.subList(0, 3), list1.subList(3, 6));
        assertTrue("copy should work on sublist of the same list", list1.equals(list2));
        list1 = getList("1,2,3,4,5,6", raList, true);
        list2 = getList("1,1,1,1,1,1", raList, false);
        ListHelper.copy(list1.subList(0, 5), list1.subList(1, 6));
        assertTrue("copy should work on sublist of the same list", list1.equals(list2));
    }

    public void testReplaceCopy()
    {
        replaceCopyTest(true);
        replaceCopyTest(false);
    }

    private static void replaceCopyTest(final boolean raList)
    {
        List list1 = getList("1,1,1,1", raList, false);
        List list2 = getList("0,0,0,0", raList, false);
        final List list3 = new ArrayList(1);
        ListHelper.replaceCopy(list1, list3, ONE, ZERO);
        assertTrue("replaceCopy should work", list3.equals(list2));
        list1 = getList("N,N,N,N", raList, false);
        ListHelper.replaceCopy(list1, list3, null, ZERO);
        assertTrue("replaceCopy should work", list3.equals(list2));
        list1 = getList("", raList, false);
        ListHelper.replaceCopy(list1, list3, ONE, ZERO);
        assertTrue("replaceCopy should have no effect on empty list", list1.equals(Collections.EMPTY_LIST));
        list1 = getList("1,2,3", raList, false);
        list2 = new ArrayList();
        ListHelper.replaceCopy(list1, list2, ZERO, ONE);
        assertTrue("replaceCopy should work even if none of the elements are replaced", list2.equals(list1));
        replaceCopyTestRandom(raList);
    }

    private static void replaceCopyTestRandom(final boolean raList)
    {
        for (int i = 0; i < 100; i++)
        {
            final List list1 = getRandomList(100, raList, false);
            final List list4 = cloneList(list1, false);
            final StringBuilder buffer = new StringBuilder(1024);
            buffer.append("original list = ").append(list4).append("\n");
            final List list2 = new ArrayList();
            ListHelper.copy(list1, list2);
            buffer.append("copied list = ").append(list2).append("\n");
            ListHelper.replace(list2, ZERO, ONE);
            buffer.append("copied and replaced list = ").append(list2).append("\n");
            final List list3 = new ArrayList(1);
            ListHelper.replaceCopy(list1, list3, ZERO, ONE);
            buffer.append("copyReplaced list = ").append(list3).append("\n");
            if (!list2.equals(list3))
            {
                assertTrue("replaceCopy should behave the same as copy followed by replace\n"
                        + buffer.toString(), false);
            }
            if (!list1.equals(list4))
            {
                assertTrue("replaceCopy should not change the inlist by any means\n"
                        + buffer.toString(), false);
            }
        }
        for (int i = 0; i < 100; i++)
        {
            final List list1 = getRandomList(10, raList, false);
            final StringBuilder buffer = new StringBuilder(1024);
            buffer.append("original list = ").append(list1).append("\n");
            final List list3 = getRandomList(20, raList, true);
            final List list4 = cloneList(list3.subList(10, 20), false);
            buffer.append("extra list = ").append(list4).append("\n");
            ListHelper.replaceCopy(list1, list3, ZERO, ONE);
            buffer.append("copyReplaced list = ").append(list3).append("\n");
            if (list3.size() < 20
                    || !list4.equals(list3.subList(10, 20)))
            {
                assertTrue("replaceCopy should not affect the element at indices more than the size of the inList\n"
                        + buffer.toString(), false);
            }
        }
        for (int i = 0; i < 100; i++)
        {
            final List list1 = getRandomList(100, raList, false);
            final List list2 = new ArrayList();
            ListHelper.copy(list1, list2);
            ListHelper.replace(list2, null, ONE);
            final List list3 = new ArrayList(1);
            ListHelper.replaceCopy(list1, list3, null, ONE);
            assertTrue("replaceCopy should behave the same as copy followed by replace for oldValue = null",
                    list2.equals(list3));
        }
    }

    public void testRemoveCopy()
    {
        removeCopyTest(true);
        removeCopyTest(false);
    }

    private static void removeCopyTest(final boolean raList)
    {
        List list1 = getList("1,2,3,2,2", raList, false);
        List list2 = cloneList(list1, true);
        List list3 = getList("1,3,3,2,2", raList, false);
        ListHelper.removeCopy(list1, list2, 2);
        assertTrue("removeCopy should work", list3.equals(list2));
        list1 = getList("N,N,3,N,N", raList, false);
        list2 = cloneList(list1, true);
        list3 = getList("3,N,3,N,N", raList, false);
        ListHelper.removeCopy(list1, list2, null);
        assertTrue("removeCopy should work", list3.equals(list2));
        removeCopyTestRandom(raList);
    }

    private static void removeCopyTestRandom(final boolean raList)
    {
        for (int i = 0; i < 100; i++)
        {
            final List list1 = getRandomList(100, raList, false);
            final List list4 = cloneList(list1, false);
            final StringBuilder buffer = new StringBuilder(1024);
            buffer.append("original list = ").append(list4).append("\n");
            final List list2 = new ArrayList();
            ListHelper.copy(list1, list2);
            buffer.append("copied list = ").append(list2).append("\n");
            ListHelper.remove(list2, ZERO);
            buffer.append("copied and removed list = ").append(list2).append("\n");
            final List list3 = new ArrayList(1);
            ListHelper.removeCopy(list1, list3, ZERO);
            buffer.append("removeCopied list = ").append(list3).append("\n");
            if (!list2.equals(list3))
            {
                assertTrue("removeCopy should behave the same as copy followed by remove\n"
                        + buffer.toString(), false);
            }
            if (!list1.equals(list4))
            {
                assertTrue("removeCopy should not change the inlist by any means\n"
                        + buffer.toString(), false);
            }
        }
        for (int i = 0; i < 100; i++)
        {
            final List list1 = getRandomList(10, raList, false);
            final StringBuilder buffer = new StringBuilder(1024);
            buffer.append("original list = ").append(list1).append("\n");
            final List list2 = new ArrayList();
            ListHelper.copy(list1, list2);
            buffer.append("copied list = ").append(list2).append("\n");
            ListHelper.remove(list2, ZERO);
            buffer.append("copied and removed list = ").append(list2).append("\n");
            final List list3 = getRandomList(20, raList, true);
            final List list4 = cloneList(list3.subList(list2.size(), 20), false);
            buffer.append("extra list = ").append(list4);
            ListHelper.removeCopy(list1, list3, ZERO);
            buffer.append("removeCopied list = ").append(list3).append("\n");
            if (!list4.equals(list3.subList(list2.size(), 20)))
            {
                assertTrue("removeCopy should not affect the extra elements in outlist\n"
                        + buffer.toString(), false);
            }
        }
        for (int i = 0; i < 100; i++)
        {
            final List list1 = getRandomList(100, raList, false);
            final List list2 = new ArrayList();
            ListHelper.copy(list1, list2);
            ListHelper.remove(list2, null);
            final List list3 = new ArrayList(1);
            ListHelper.removeCopy(list1, list3, null);
            assertTrue("removeCopy should behave the same as copy followed by remove for oldValue = null",
                    list2.equals(list3));
        }
    }

    public void testUniqueCopy()
    {
        uniqueCopyTest(true);
        uniqueCopyTest(false);
    }

    private static void uniqueCopyTest(final boolean raList)
    {
        uniqueCopyTestRandom(raList);
        final List list1 = getList("1,N,N,2,2", raList, false);
        final List list2 = new ArrayList();
        ListHelper.uniqueCopy(list1, list2);
        assertTrue("uniqueCopy should work for null too", list2.equals(getList("1,N,2", raList, false)));
    }

    private static void uniqueCopyTestRandom(final boolean raList)
    {
        for (int i = 0; i < 100; i++)
        {
            final List list1 = getRandomList(10, raList, true);
            Collections.sort(list1, new NullLowComparator());
            final List list4 = cloneList(list1, false);
            final StringBuilder buffer = new StringBuilder(1024);
            buffer.append("original list = ").append(list4).append("\n");
            final List list2 = new ArrayList();
            ListHelper.copy(list1, list2);
            buffer.append("copied list = ").append(list2).append("\n");
            ListHelper.unique(list2);
            buffer.append("copied and uniqued list = ").append(list2).append("\n");
            final List list3 = new ArrayList(1);
            ListHelper.uniqueCopy(list1, list3);
            buffer.append("uniqueCopied list = ").append(list3).append("\n");
            if (!list2.equals(list3))
            {
                assertTrue("uniqueCopy should behave the same as copy followed by unique\n"
                        + buffer.toString(), false);
            }
            if (!list1.equals(list4))
            {
                assertTrue("removeCopy should not change the inlist by any means\n"
                        + buffer.toString(), false);
            }
        }
        for (int i = 0; i < 100; i++)
        {
            final List list1 = getRandomList(10, raList, true);
            ListHelper.sort(list1, new NullLowComparator());
            final StringBuilder buffer = new StringBuilder(1024);
            buffer.append("original list = ").append(list1).append("\n");
            final List list2 = new ArrayList();
            ListHelper.copy(list1, list2);
            buffer.append("copied list = ").append(list2).append("\n");
            ListHelper.unique(list2);
            buffer.append("copied and uniqued list = ").append(list2).append("\n");
            final List list3 = getRandomList(20, raList, true);
            final List list4 = cloneList(list3.subList(list2.size(), 20), false);
            buffer.append("extra list = ").append(list4);
            ListHelper.uniqueCopy(list1, list3);
            buffer.append("uniqueCopied list = ").append(list3).append("\n");
            if (!list4.equals(list3.subList(list2.size(), 20)))
            {
                assertTrue("uniqueCopy should not affect the extra elements in outlist\n"
                        + buffer.toString(), false);
            }
        }
    }

    public void testReverseCopy()
    {
        reverseCopyTest(true);
        reverseCopyTest(false);
    }

    private static void reverseCopyTest(final boolean raList)
    {
        final List list1 = getList("", raList, false);
        final List list2 = new ArrayList();
        ListHelper.reverseCopy(list1, list2);
        assertTrue("reverseCopy should work on empty list too", Collections.EMPTY_LIST.equals(list2));
        reverseCopyTestRandom(raList);
    }

    private static void reverseCopyTestRandom(final boolean raList)
    {
        for (int i = 0; i < 100; i++)
        {
            final StringBuilder buffer = new StringBuilder(1024);
            final List list1 = getRandomList(10, raList, true);
            final List list2 = cloneList(list1, false);
            buffer.append("original inlist = ").append(list1).append("\n");
            final List list3 = getRandomList(20, raList, true);
            final List list4 = cloneList(list3.subList(10, 20), false);
            buffer.append("original outlist = ").append(list3).append("\n");
            ListHelper.reverseCopy(list1, list3);
            buffer.append("reverseCopied list = ").append(list3).append("\n");
            if (!list1.equals(list2))
            {
                assertTrue("reverseCopy should not affect the inList in any way\n"
                        + buffer.toString(), false);
            }
            ListHelper.reverse(list1);
            if (!list1.equals(list3.subList(0, 10)))
            {
                assertTrue("reverseCopy should work\n" + buffer.toString(), false);
            }
            if (!list4.equals(list3.subList(10, 20)))
            {
                assertTrue("reverseCopy should not affect the extra elements in outlist\n"
                        + buffer.toString(), false);
            }
        }
    }

    public void testLexicographicalCompare()
    {
        lexicographicalCompareTest(true);
        lexicographicalCompareTest(false);

    }

    private static void lexicographicalCompareTest(final boolean raList)
    {
        final List list1 = getList("1,2,3", raList, false);
        assertEquals("same lists should be lexicographically equivalent", 0,
                ListHelper.lexicographicalCompare(list1, list1));
        final List list2 = getList("1,2,3,4", raList, false);
        assertEquals("lexicographicalCompare should work", -4,
                ListHelper.lexicographicalCompare(list1, list2));
        assertEquals("lexicographicalCompare should work", 4,
                ListHelper.lexicographicalCompare(list2, list1));
        assertEquals("lexicographicalCompare should work for empty lists too", -1,
                ListHelper.lexicographicalCompare(Collections.EMPTY_LIST, list1));
        assertEquals("lexicographicalCompare should work for empty lists too", 0,
                ListHelper.lexicographicalCompare(Collections.EMPTY_LIST, Collections.EMPTY_LIST));
    }

    @SuppressWarnings({"BooleanMethodNameMustStartWithQuestion"})
    private static boolean xor(final boolean bol1, final boolean bol2)
    {
        return (bol1 && !bol2) || (!bol1 && bol2);
    }

    private static String listsInTest(final List<?>... lists)
    {
        final StringBuilder buf = new StringBuilder(100);
        buf.append("Testing with the following lists : ");
        for (final List<?> list : lists)
        {
            buf.append(list).append(" ");
        }
        return buf.toString();
    }

    /*
     * when passed something like 1,2,3,4 it returns a list of those integers
     */
    @SuppressWarnings({"ReturnOfNull"})
    private static List<Integer> getList(final String str, final boolean raList, final boolean modifiable)
    {
        if (str == null)
        {
            return null;
        }
        if ("".equals(str.trim()))
        {
            return Collections.EMPTY_LIST;
        }
        final StringTokenizer st = new StringTokenizer(str, ",");
        final List<Integer> list = raList ? new ArrayList<Integer>() : new LinkedList<Integer>();
        while (st.hasMoreTokens())
        {
            final String token = st.nextToken().trim();
            if ("N".equalsIgnoreCase(token.trim()))
            {
                list.add(null);
            }
            else
            {
                list.add(new Integer(token));
            }
        }
        return (modifiable) ? list : Collections.unmodifiableList(list);
    }

    private static final Integer ZERO = 0;
    private static final Integer ONE = 1;
    private static final Integer TWO = 2;

    private static final Random rnd = new Random();

    private static List<Integer> getRandomList(final boolean raList)
    {
        return getRandomList(rnd.nextInt(10), raList, true);
    }

    private static List<Integer> getRandomList(final int size, final boolean raList, final boolean modifiable)
    {
        final List<Integer> list = createEmptyList(raList, size);
        for (int i = 0; i < size; i++)
        {
            final int random = rnd.nextInt(10);
            if (random == 9)
            {
                list.add(null);
            }
            else
            {
                list.add(random);
            }
        }
        return (modifiable) ? list : Collections.unmodifiableList(list);
    }

    @SuppressWarnings({"ReturnOfNull"})
    private static List<Integer> cloneList(final List<Integer> list, final boolean modifiable)
    {
        if (list == null)
        {
            return null;
        }
        final List<Integer> list2 = createEmptyList(list instanceof RandomAccess, list.size());
        final ListIterator itr1 = list.listIterator();
        final ListIterator itr2 = list2.listIterator();
        while (itr1.hasNext())
        {
            itr2.add(itr1.next());
        }
        return (modifiable) ? list2 : Collections.unmodifiableList(list2);
    }

    private static List<Integer> getRandomSortedList(final boolean raList, final boolean modifiable)
    {
        final List<Integer> list = getRandomList(raList);
        ListHelper.sort(list);
        return (modifiable) ? list : Collections.unmodifiableList(list);
    }

    private static AbstractList<Integer> createEmptyList(final boolean raList, final int size)
    {
        return raList ? new ArrayList<Integer>(size) : new LinkedList<Integer>();
    }

    static final class NullLowComparator implements Comparator
    {

        public int compare(final Object obj1, final Object obj2)
        {
            if (obj1 == null)
            {
                return (obj2 == null) ? 0 : -1;
            }
            else
            {
                return (obj2 == null) ? 1 : ((Comparable) obj1).compareTo(obj2);
            }
        }

    }

}
